#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// 定义元素类型
typedef int ElemType;
// 定义动态数组
typedef struct {
    ElemType *data;
    int length;
} SSTable;

/**
 * 动态数组初始化
 * @param A
 * @param length
 */
void ST_Init(SSTable &A, int length) {
    A.length = length;
    A.data = (ElemType*) malloc(sizeof (ElemType) * length);
    // 生成随机序列
    srandom(time(NULL));
    for (int i = 0; i < length; ++i) {
        A.data[i] = random() % 100;
    }
}

/**
 * 打印动态数组
 * @param A
 */
void ST_Print(SSTable A) {
    for (int i = 0; i < A.length; ++i) {
        printf("%3d", A.data[i]);
    }
    printf("\n");
}

/**
 * 元素位置交换
 * @param a
 * @param b
 */
void swap(ElemType &a, ElemType &b) {
    ElemType tmp = a;
    a = b;
    b = tmp;
}

/**
 * 调整子树
 * @param A         带调整的堆
 * @param k         需要调整的结点下标
 * @param length    数组长度
 */
void AdjustDown(SSTable &A, int k, int length) {
    int parent = k;             // 父结点下标
    int child = 2 * k + 1;      // 左孩子下标
    while(child < length) {
        if (child + 1 < length && A.data[child] <= A.data[child+1]) {
            child++;
        }
        if (A.data[parent] < A.data[child]) {
            swap(A.data[parent], A.data[child]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

/**
 * 堆排序
 * 调整子树时只遍历被调整过的子树
 * @param A
 */
void HeapSort(SSTable &A) {
    // 调整为大根堆
    // 需注意：计算父结点用的是数组长度还是最后一个元素的下标
    for (int i = (A.length-1) / 2; i >= 0; --i) {
        AdjustDown(A, i, A.length);
    }
    // 交换顶部与最后一个元素
    swap(A.data[0], A.data[A.length - 1]);
    for (int i = A.length-1; i >= 0; --i) {
        AdjustDown(A, 0, i);
        swap(A.data[0], A.data[i-1]);
    }
}


/**
 * 实现动态数组的堆排序
 * @return
 */
int main() {
    SSTable A;
    ST_Init(A, 10);
    ST_Print(A);

    HeapSort(A);
    ST_Print(A);

    return 0;
}